package com.jhxy.algorithm.twosum;

import java.util.Arrays;

/**
 * 两数之和:二分查找
 */
public class BinarySearchTwoNumberSum {


    public int[] twoSum(int[] nums, int target) {
        int[] sortedNums = nums.clone();
        int[] res = new int[2];
        Arrays.sort(sortedNums);

        res[0] = -1;
        res[1] = -1;

        for (int i = 0; i < sortedNums.length; i++) {
            int index = findNumIndexInSortedArray(sortedNums, target - sortedNums[i], i + 1);
            if (index != -1) {
                res[0] = getNumberIndex(nums, sortedNums[i], -1);
                res[1] = getNumberIndex(nums, sortedNums[index], res[0]);
            }
        }

        return res;
    }


    public int getNumberIndex(int[] nums, int target, int forbiddenIndex) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target && i != forbiddenIndex) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 对于有序数组,通过二分算法，找到target目标值所在角标位置
     *
     * @param nums       有序数组
     * @param target     目标值
     * @param startIndex 起始角标
     * @return target所在角标
     */
    public int findNumIndexInSortedArray(int[] nums, int target, int startIndex) {
        int index = -1;
        int leftIndex = startIndex;
        int rightIndex = nums.length - 1;

        while (leftIndex <= rightIndex) {
            int midIndex = (rightIndex - leftIndex) / 2 + leftIndex;
            if (nums[midIndex] == target) {
                return midIndex;
            }

            //左移-> 中间值大于target,rightIndex左移到midIndex的位置
            if (nums[midIndex] > target) {
                rightIndex = midIndex - 1;
            }

            //右移 -> 中间值小于target，leftIndex右移到midIndex的位置
            if (nums[midIndex] < target) {
                leftIndex = midIndex + 1;
            }
        }

        return index;
    }


    public static void main(String[] args) {
        InputForTwoNumberSum ins = new InputForTwoNumberSum("0,4,2,1,2,3,2,3,4,4,4", "8");

        BinarySearchTwoNumberSum bs = new BinarySearchTwoNumberSum();

        for (int i : bs.twoSum(ins.nums, ins.target)) {
            System.out.println(i);
        }
    }
}
